P4458 [BJOI2018]链上二次求和

发表于

闲扯

不愧是一道省选题，感觉做着还是很有难度的。

题面

P4458 [BJOI2018]链上二次求和

Solution

我们先把题意简化出来。

给出一序列，有以下两个操作：

  • 给区间 $[l,r]$ 内的每一个数加上 $d$ 。
  • 询问长度在 $[l,r]$ 之间的连续子序列的权值和。

设 $sum_k=\sum_{i=1}^k val_i$ ，那么我们要求的东西就是

我们设 $s_k=\sum_{i=1}^k sum_i$ 。

那么我们最终要求的东西就是

这个我们用线段树来维护，即可将单次询问的时间复杂度降低至 $O(\log n)$ 。

然后考虑区间加的时候，每一个 $s_k$ 会怎么变。

设 $f(i)=\frac{i\cdot (i+1)}{2}$ 。

简单画个图，推一下，可以发现：

  • 对于 $\forall k\in[l,r]$ ，我们有 $s_k+=f(k-l+1)\cdot d$ 。
  • 对于 $\forall k\in(r+1,n]$ ，我们有 $s_k+=f(r-l+1)\cdot d+d\cdot (r-l+1)\cdot (k-r)$ 。

考虑怎么用线段树维护这个式子。

对于 $k\in[l,r]$ ，我们有 $s_k+=\frac{k^2+(3-2l)k+(l^2-3l+2)}{2}\cdot d$ 。

对于 $k\in(r,n]$ ，我们有 $s_k+=(r-l+1)d+(r-l+1)(\frac{r-l+2}{2}-r)$ 。

所以我们分别维护出 $\sum i^2,\sum i,1$ 的懒标记即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 2e5+5,mod = 1e9+7;
const int inv6=166666668;
const int inv2=500000004;
int n,m,val[MAXN],opt,x,y,k,sum[MAXN];
it add(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
it mul(int x,int y){
	return 1ll*x*y%mod;
}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
	int sum,t1,t2,t3;
}T[MAXN<<2];
it s1(int x){
	return mul(mul(x,x+1),inv2);
}
it s2(int x){
	return mul(mul(mul(x,x+1),x*2+1),inv6);
}
il upd(int cur,int l,int r,int a,int b,int c){
	T[cur].t1=add(T[cur].t1,a);
	T[cur].t2=add(T[cur].t2,b);
	T[cur].t3=add(T[cur].t3,c);
	T[cur].sum=add(T[cur].sum,mul(a,add(s2(r),mod-s2(l-1))));
	T[cur].sum=add(T[cur].sum,mul(b,add(s1(r),mod-s1(l-1))));
	T[cur].sum=add(T[cur].sum,mul(c,r-l+1));
}
il pushup(int cur){
	T[cur].sum=add(T[lc].sum,T[rc].sum);
}
il pushdown(int cur,int l,int r){
	if(T[cur].t1==0&&T[cur].t2==0&&T[cur].t3==0)
		return ;
	upd(lc,l,mid,T[cur].t1,T[cur].t2,T[cur].t3);
	upd(rc,mid+1,r,T[cur].t1,T[cur].t2,T[cur].t3);
	T[cur].t1=T[cur].t2=T[cur].t3=0;
}
il Build(int cur,int l,int r){
	if(l==r){
		T[cur].sum=sum[l];
		return ;
	}
	Build(lc,l,mid),Build(rc,mid+1,r);
	pushup(cur);
}
il Updata(int cur,int l,int r,int L,int R,int a,int b,int c){
	if(l>=L&&r<=R){
		upd(cur,l,r,a,b,c);
		return ;
	}
	pushdown(cur,l,r);
	if(mid>=L)
		Updata(lc,l,mid,L,R,a,b,c);
	if(R>mid)
		Updata(rc,mid+1,r,L,R,a,b,c);
	pushup(cur);
}
it Query(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R)
		return T[cur].sum;
	pushdown(cur,l,r);
	ri res=0;
	if(mid>=L)
		res=add(res,Query(lc,l,mid,L,R));
	if(R>mid)
		res=add(res,Query(rc,mid+1,r,L,R));
	return res;
}
int main(){
//	freopen("sum.in","r",stdin);
//	freopen("sum.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i)
		read(val[i]);
	for(ri i=1;i<=n;++i)
		sum[i]=add(sum[i-1],val[i]);
	for(ri i=1;i<=n;++i)
		sum[i]=add(sum[i-1],sum[i]);
	Build(1,0,n);
	for(ri i=1;i<=m;++i){
		read(opt),read(x),read(y);
		if(x>y)
			swap(x,y);
		if(opt==1){
			read(k);
			Updata(1,0,n,x,y,mul(inv2,k),mul(mul(add(3,mod-2*x),inv2),k),mul(mul(add(mul(x,x)+2,mod-mul(3,x)),inv2),k));
			if(y<n)
				Updata(1,0,n,y+1,n,0,mul(k,y-x+1),mul(mul(y-x+1,k),add(mul(y-x+2,inv2),mod-y)));
		}
		if(opt==2){
			ri res=mul(Query(1,0,n,n,n),y-x+1);
			res=add(res,mod-Query(1,0,n,x-1,y-1));
			res=add(res,mod-Query(1,0,n,n-y,n-x));
			print(res),puts("");
		}
	}
	return 0;
}